#ifndef PROJECTS_BINARY_PATTERNS_BINARY_PATTERNS_H
#define PROJECTS_BINARY_PATTERNS_BINARY_PATTERNS_H

#include <string>

#include "grate/antidictionary.h"
#include "grate/util/word.h"

namespace growth_rate {
namespace binary_patterns {

// Requires: 1) buffer must have sufficient size.
//           2) pattern contains only symbols "x" and "y".
Word build_xy_pattern(uint8_t *buffer, const std::string &pattern,
                      const Word &X, const Word &Y);
bool is_xy_pattern(const Word &word, const std::string &pattern,
                   size_t xlen, size_t ylen);

// ------ Antidictionaries -------
class BinaryPatternAD : public LexminAntiDictionary {
 public:
  struct Options {
    std::string pattern;
    size_t max_root_length;
    size_t queue_capacity;
    size_t trie_capacity;
  };

  explicit BinaryPatternAD(const Options &options)
    : LexminAntiDictionary(options.trie_capacity, 2),
      options_(options),
      max_queue_size_(0) { }
  virtual size_t extra_memory_usage() const { return max_queue_size_; }

 protected:
  bool can_extend_root(Word *root, char letter,
                       bool check_length = true) const {
    DCHECK(letter == 'a' || letter == 'b');
    if (check_length &&
        root->length() + 1 > options_.max_root_length) return false;
    Word nroot = root->append(letter);
    for (size_t suff_len = 2; suff_len <= nroot.length(); suff_len++) {
      if (!trie_accepts_word(nroot.suffix(suff_len), Forward))
        return false;
    }
    return true;
  }

  const Options options_;
  size_t max_queue_size_;
};

class Pattern_XYXYXX : public BinaryPatternAD {
 public:
  using BinaryPatternAD::Options;
  explicit Pattern_XYXYXX(const Options &options)
    : BinaryPatternAD(options) { }

 private:
  bool construct();
  bool handle_xy_root(const Word &root, size_t xlen);
};

// Supports patterns: xyxxyxy, xyxyyxx (optionally, with xxx).
class Pattern_4X_3Y : public BinaryPatternAD {
 public:
  using BinaryPatternAD::Options;
  Pattern_4X_3Y(const Options &options, bool avoid_xxx = false)
    : BinaryPatternAD(options), avoid_xxx_(avoid_xxx) { }

 private:
  bool construct();
  bool handle_xy_root(const Word &root, size_t xlen);
  bool handle_cubic_root(const Word &root);

  bool avoid_xxx_;
};

// Supports pattern: xyxxyyxy (optionally, with xxx).
class Pattern_4X_4Y : public BinaryPatternAD {
 public:
  using BinaryPatternAD::Options;
  Pattern_4X_4Y(const Options &options, bool avoid_xxx = false)
    : BinaryPatternAD(options), avoid_xxx_(avoid_xxx) { }

 private:
  bool construct();
  bool handle_xy_root(const Word &root, size_t xlen);
  bool handle_cubic_root(const Word &root);

  bool avoid_xxx_;
};

LexminAntiDictionary *get_antidictionary_for_pattern(
    const std::string &pattern, size_t root_length,
    size_t queue_capacity = 0, size_t trie_capacity = 0);

}  // namespace binary_patterns
}  // namespace growth_rate

#endif  // PROJECTS_BINARY_PATTERNS_BINARY_PATTERNS_H
